#pragma once
#include<iostream>
#include<bitset>
#include<vector>
using namespace std;
 
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		// BKDR
		size_t value = 0;
		for (auto ch : s)
		{
			value *= 31;
			value += ch;
		}
		return value;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string & s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};
namespace dj
{
	template<size_t N,class K = string,class Hash1 = BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>
	class BloomFilter
	{
	public:
		void set(const K& s)
		{
			size_t hash1 = Hash1()(s) % N;
			size_t hash2 = Hash2()(s) % N;
			size_t hash3 = Hash3()(s) % N;
			_bit.set(hash1);
			_bit.set(hash2);
			_bit.set(hash3);
		}
		bool test(const K& s)
		{
			size_t hash1 = Hash1()(s)%N;
			size_t hash2 = Hash2()(s)%N;
			size_t hash3 = Hash3()(s)%N;
			return _bit.test(hash1) && _bit.test(hash2) && _bit.test(hash3);
		}

	private:
		std::bitset<N>_bit;
	};
}


